04. Big O Notation (1/2)

Big O Notation

When describing the efficiency of an algorithm, we could say something like "the run-time of the algorithm increases linearly with the input size". This can get wordy and it also lacks precision. So as an alternative, mathematicians developed a form of notation called big O notation.

The "O" in the name refers to the order of the function or algorithm in question. And that makes sense, because big O notation is used to describe the order—or rate of increase—in the run-time of an algorithm, in terms of the input size (n).

In this next video, Brynn will show some different examples of what the notation would actually look like in practice. This likely won't "click" for you right away, but don't worry—once you've gotten some experience applying it to real problems, it will be much more concrete.

Notation Intro V3

When you see some Big O notation, such as O(2n + 2), what does n refer to?
SOLUTION: The length of the input to your algorithm.

Here's the cipher pseudocode Brynn showed in the video:

function decode(input):
    create output string
    for each letter in input:
        get new_letter from letter's location in cipher
        add new_letter to output
    return output

Brynn estimated the efficiency as O(2n + 2). Suppose the input string is "jzqh". What is n in this case?
SOLUTION: 4

Which of these is the same as O(1)?
SOLUTION: **O(0n + 1)**

Here's one of the functions we looked at on the last page:

def say_hello(n):
    for i in range(n):
        print("Hello!")

Which of these would best approximate the efficiency using big O notation?
SOLUTION: n

Here's the other function we looked at on the last page:

def say_hello(n):
    for i in range(n):
        for i in range(n):
            print("Hello!")

Again, which of these would best approximate the efficiency using big O notation?
SOLUTION: n^2

Next Concept